/*
Merge.java
Paola Garcia, 10205
08 agosto 2011
Descripcion: Hoja de trabajo 3.
Clase que realiza el sortin por medio de Merge sort
visto en el libro de JavaStructures
*/

public class Merge{
	
	public Merge(){
	
	}
		
		//ordenar los numeros 
		private static void mergeSorting(int[] num, int[] num1, int bajo, int medio, int alto){
			
			//declaracion de variables
			int resultado = bajo;
			int resultado1 = bajo;
			int destino = medio;
			
			//Encontrar el valor menor
			
			while(resultado1 < medio && destino <= alto){
				if(num[destino] < num1[resultado1])					
					num[resultado ++] = num[destino ++];
				else
					num[resultado ++] = num1[resultado1 ++];
			}
			
			while(resultado1 < medio){
				num[resultado ++] = num1[resultado1 ++];
			}
		}
		
		//ordenar los valores
		private static void mergeSortRecursive(int[] num, int[] num1, int bajo, int alto){
			
			int n = alto - bajo + 1;
			int medio = bajo + n/2;
			int var;
			
			if(n < 2)
				return;
			for(var = bajo; var < medio; var ++){
				num1[var] = num[var];
			}
			
			//ordenar todos los numeros
			mergeSortRecursive(num1, num, bajo, medio-1);
			mergeSortRecursive(num, num1, medio, alto);
			mergeSorting(num, num1, bajo, medio, alto);
		
		}
		
		//ordenar numeros
		public static void mergeSort(int num[], int n){
			mergeSortRecursive(num,new int[n],0,n-1);
		}
		
}
